Лабораторная работа №4

Цель лабораторной работы

1. Реализовать на языке программирования алгоритмы Евклида для вычисления наибольшего общего делителя

Теоретическое введение

Целое число d ≠ 0 называется наибольшим общим делителем целых чисел a₁, a₂, ..., a_k (обозначается d= НОД (a₁,a₂,...,a_k)), если выполняются следующие условия:

• каждое из чисел a₁, a₂, ..., a_k делится на d,

• если d₁ ≠ 0 - другой общий делитель чисел a₁, a₂, ..., a_k, то d делится на d₁.

Для вычисления наибольшего общего делителя двух целых чисел применяется способ повторного деления с остатком, называемый алгоритмом Евклида.

Теоретическое введение

Бинарный алгоритм Евклида основан на следующих свойствах наибольшего общего делителя (считаем, что 0 < b ≤ a):

1. если оба числа a и b четные, то НОД(a,b) = 2* НОД$(\frac {a}{2}, \frac{b}{2})$

2. если число a - нечетное, число b -четное, то НОД(a,b)= НОД$(a, \frac{b}{2})$

3. если оба числа a и b нечетные, a > b, то НОД(a,b)= НОД(a−b,b)

4. если a = b, то НОД(a,b) = a

Ход выполнения лабораторной работы

• Реализуем алгоритм Евклида

Ход выполнения лабораторной работы

• Реализуем бинарный алгоритм Евклида

Ход выполнения лабораторной работы

• Реализуем расширенный алгоритм Евклида

Ход выполнения лабораторной работы

• Реализуем расширенный бинарный алгоритм Евклида

Вывод

• В ходе выполнения данной лабораторной работы были реализованы алгоритмы Евклида для вычисления наибольшего общего делителя